package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/11/30 22:46
 * @description：https://leetcode-cn.com/problems/nth-digit/
 */
public class 第N位数字 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.findNthDigit(Integer.MAX_VALUE - 1));
    }

    /*
    class Solution {
        public int findNthDigit(int n) {
            if (n <= 9) return n;
            long factor = 9;
            int index = 1;
            long pre = 0;
            long sum = factor * index;
            while (n > sum) {
                factor *= 10;
                index++;
                pre = sum;
                sum += factor * index;
            }
            n -= pre;
            int firsNum = (int) (factor / 9);
            int num = firsNum + (n - 1) / index;
            int digitIndex = (n - 1) % index;
            int digit = (num / (int)(Math.pow(10, index - digitIndex - 1))) % 10;
            return digit;
        }
    }
     */

    class Solution {
        public int findNthDigit(int n) {
            int index = 1, factor = 9;
            while (n > (long) index * factor) {
                n -= index * factor;
                index++;
                factor *= 10;
            }
            int start = factor / 9;
            int num = start + (n - 1) / index;
            int digitIndex = (n - 1) % index;
            int digit = (num / (int)(Math.pow(10, index - digitIndex - 1))) % 10;
            return digit;
        }
    }

}
